{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #N-th Tribonacci Number"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #memoization #math #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #记忆化搜索 #数学 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: tribonacci"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #第 N 个泰波那契数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>泰波那契序列&nbsp;T<sub>n</sub>&nbsp;定义如下：&nbsp;</p>\n",
    "\n",
    "<p>T<sub>0</sub> = 0, T<sub>1</sub> = 1, T<sub>2</sub> = 1, 且在 n &gt;= 0&nbsp;的条件下 T<sub>n+3</sub> = T<sub>n</sub> + T<sub>n+1</sub> + T<sub>n+2</sub></p>\n",
    "\n",
    "<p>给你整数&nbsp;<code>n</code>，请返回第 n 个泰波那契数&nbsp;T<sub>n </sub>的值。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 4\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>\n",
    "T_3 = 0 + 1 + 1 = 2\n",
    "T_4 = 1 + 1 + 2 = 4\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>n = 25\n",
    "<strong>输出：</strong>1389537\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= n &lt;= 37</code></li>\n",
    "\t<li>答案保证是一个 32 位整数，即&nbsp;<code>answer &lt;= 2^31 - 1</code>。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [n-th-tribonacci-number](https://leetcode.cn/problems/n-th-tribonacci-number/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [n-th-tribonacci-number](https://leetcode.cn/problems/n-th-tribonacci-number/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4', '25']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        a,b,c=0,1,1\n",
    "        for i in range(1,n+1):\n",
    "            a,b,c=b,c,a+b+c\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n):\n",
    "        arrays = [0, 1, 1]\n",
    "        for i in range(3, n + 1):\n",
    "            arrays.append(arrays[i - 1] + arrays[i - 2] + arrays[i - 3])\n",
    "        return arrays[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        \n",
    "        dp = [0] * (n + 1)\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n <= 2:\n",
    "            return 1\n",
    "        dp[0] = 0\n",
    "        dp[1] = 1\n",
    "        dp[2] = 1\n",
    "        \n",
    "\n",
    "        for i in range(3, n+1):\n",
    "            dp[i] = dp[i-1] + dp[i-2] + dp[i-3]\n",
    "\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        a, b, c = 0, 1, 1\n",
    "        for _ in range(n):\n",
    "            a, b, c = b, c, a+b+c \n",
    "        return a "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        elif n == 1 or n == 2:\n",
    "            return 1\n",
    "        a, b, c = 0, 1, 1\n",
    "        for i in range(n-2):\n",
    "            a, b, c = b, c, a+b+c \n",
    "        return c\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        f = [0,1,1]\n",
    "        if n<=2: return f[n]\n",
    "        for i in range(n-2):\n",
    "            f.append(f[-1]+f[-2]+f[-3])\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        if n ==0:\n",
    "            return 0\n",
    "        if n<=2:\n",
    "            return 1\n",
    "        a,b,c,i = 0,1,1,2\n",
    "        while i<n:\n",
    "            a,b,c=b,c,a+b+c\n",
    "            i +=1\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def tribonacci(self, n: int) -> int:\n",
    "#         if n == 0:return 0\n",
    "#         if n == 1:return 1\n",
    "#         if n == 2:return 1\n",
    "#         return self.tribonacci(n-1) + self.tribonacci(n-2) + self.tribonacci(n-3)\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        t = [0, 1, 1]\n",
    "        if n <= 2: return t[n]\n",
    "        for _ in range(3, n+1):\n",
    "            t.append(t[-1] + t[-2] + t[-3])\n",
    "        return t[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 0\n",
    "        if n==1 or n==2 :\n",
    "            return 1\n",
    "        dp=[1]*n\n",
    "        dp[2]=2\n",
    "        for i in range(3,n):\n",
    "            dp[i]=dp[i-1]+dp[i-2]+dp[i-3]\n",
    "        return dp[n-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        a, b, c = 0, 1, 1\n",
    "        if n == 0:\n",
    "            return a\n",
    "        elif n == 1:\n",
    "            return b\n",
    "        for _ in range(n-2):\n",
    "            a, b, c = b, c, a+b+c\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        T = [0,1,1]\n",
    "        if n < 3:\n",
    "            return T[n]\n",
    "        while len(T) <= n:\n",
    "            T.append(T[-1] + T[-2] + T[-3])\n",
    "        return T[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 0\n",
    "        if n<=2:\n",
    "            return 1\n",
    "        p, q, r ,m= 0, 0, 1, 1\n",
    "        for i in range(2, n + 1):\n",
    "            p= q\n",
    "            q= r\n",
    "            r= m\n",
    "            m= p+q+r\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        a = 0\n",
    "        b = 1\n",
    "        c = 1\n",
    "        while n > 0:\n",
    "            a, b, c = b, c, a+b+c\n",
    "            n -= 1\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        elif n == 1 or n == 2:\n",
    "            return 1\n",
    "        \n",
    "        l = [0,1,1]\n",
    "        n = n - 2\n",
    "        while n > 0:\n",
    "            result = sum(l)\n",
    "            l.append(result)\n",
    "            l.pop(0)\n",
    "            n += - 1\n",
    "        return result\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        zero_num = 0\n",
    "        first_num = 1\n",
    "        second_num = 1\n",
    "\n",
    "        if n == 0:\n",
    "            return zero_num\n",
    "        if n == 1:\n",
    "            return first_num\n",
    "        if n == 2:\n",
    "            return second_num\n",
    "        \n",
    "        nth_num = 0\n",
    "        for i in range(3, n+1):\n",
    "            nth_num = zero_num + first_num + second_num\n",
    "\n",
    "            zero_num = first_num\n",
    "            first_num = second_num\n",
    "            second_num = nth_num\n",
    "        \n",
    "        return nth_num\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return n\n",
    "        elif n == 1 or n == 2:\n",
    "            return 1\n",
    "        p = 0\n",
    "        q = r = 1\n",
    "        for i in range(3,n + 1):\n",
    "            s = p + q + r\n",
    "            p,q,r = q,r,s\n",
    "        return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        if n <= 1:\n",
    "            return n\n",
    "        if n == 2:\n",
    "            return 1\n",
    "        t0 = 0\n",
    "        t1 = 1\n",
    "        t2 = 1\n",
    "        ans = 0\n",
    "        for _ in range(n-2):\n",
    "            ans = t0 + t1 + t2 \n",
    "            t0, t1, t2 = t1, t2, ans\n",
    "            \n",
    "        return ans     \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        res = [0, 1, 1]\n",
    "        if n <= 2:\n",
    "            return res[n]\n",
    "            \n",
    "        for i in range(3, n+1):\n",
    "            tmp = sum(res[i-3:i])\n",
    "            res.append(tmp)\n",
    "        return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        if n==0:return 0\n",
    "        a,b,c=0,1,1\n",
    "        for i in range(n-2):\n",
    "            a,b,c=b,c,a+b+c\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        elif n == 1:\n",
    "            return 1\n",
    "        elif n == 2:\n",
    "            return 1\n",
    "        else:\n",
    "            arr = (n+1) * [0]\n",
    "            arr[0] = 0\n",
    "            arr[1] = 1\n",
    "            arr[2] = 1\n",
    "            for i in range(3,n + 1):\n",
    "                arr[i] = arr[i-1] + arr[i-2] + arr[i-3]\n",
    "            return arr[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        a = 0\n",
    "        b = c = 1\n",
    "        if 0 <= n <1:\n",
    "            return a\n",
    "        if 1 <= n <3:\n",
    "            return b\n",
    "        for i in range(3, n+1):\n",
    "            r = a + b + c\n",
    "            a = b\n",
    "            b = c\n",
    "            c = r\n",
    "        return r "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        dp = [0,1,1]\n",
    "        if n < 2:\n",
    "            return n\n",
    "\n",
    "\n",
    "        for _ in range(n):\n",
    "            dp.append(dp[-1]+dp[-2]+dp[-3])\n",
    "        return dp[n]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def cache(func):\n",
    "        cache_list={}\n",
    "        def wrapper(self, n):\n",
    "            if n in cache_list:\n",
    "                return cache_list[n]\n",
    "            res = func(self, n)\n",
    "            cache_list[n] = res\n",
    "            return res\n",
    "        return wrapper\n",
    "\n",
    "    @cache\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 0\n",
    "        elif n==1 or n==2:\n",
    "            return 1\n",
    "        return self.tribonacci(n-3)+ self.tribonacci(n-2)+ self.tribonacci(n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        if n < 2:\n",
    "            return n\n",
    "        elif n == 2:\n",
    "            return 1\n",
    "        a, b, c = 0, 1, 1\n",
    "        for i in range(3, n + 1):\n",
    "            a, b, c = b, c, a+b+c \n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 0\n",
    "        if n==1 or n==2:\n",
    "            return 1\n",
    "        else:\n",
    "            ans = [0] * (n+1)\n",
    "            ans[1] = ans [2] = 1\n",
    "            # if n==0:\n",
    "            #     return 0;\n",
    "            # if n==1 || n==2:\n",
    "            #     return 1;\n",
    "            for i in range(3,n+1):\n",
    "                ans[i] = ans[i-1]+ans[i-2]+ans[i-3]\n",
    "\n",
    "        return ans[-1]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        dp = [0, 1, 1]\n",
    "        for i in range(3, n+1):\n",
    "            dp.append(dp[i-1] + dp[i-2] + dp[i-3])\n",
    "\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        a = [0,1,1]\n",
    "        for i in range(3,n+1):\n",
    "            a.append(a[i-3]+a[i-2]+a[i-1])\n",
    "        return a[n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        fibli = list([0,1,1])\n",
    "        for _ in range(n):\n",
    "            fibli.append(fibli[-1]+fibli[-2]+fibli[-3])\n",
    "        return fibli[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 0\n",
    "        if n==1 or n==2:\n",
    "            return 1\n",
    "        dp=[0 for i in range(n+1)]\n",
    "        dp[0]=0\n",
    "        dp[1]=1\n",
    "        dp[2]=1\n",
    "        for i in range(3,n+1):\n",
    "            dp[i]=dp[i-1]+dp[i-2]+dp[i-3]\n",
    "        \n",
    "        return dp[n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        if(n==0):\n",
    "            return 0\n",
    "        if(n<3):\n",
    "            return 1\n",
    "\n",
    "        t0 ,t1, t2 = 0,1,1\n",
    "        for i in range(3,n+1):\n",
    "            t3 = t0+t1+t2\n",
    "            t0 = t1\n",
    "            t1 = t2\n",
    "            t2 = t3\n",
    "        return t3\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n <= 2:\n",
    "            return 1\n",
    "        \n",
    "        p = 0\n",
    "        q = r = 1\n",
    "        for i in range(3, n + 1):\n",
    "            s = p + q + r\n",
    "            p, q, r = q, r, s\n",
    "        return s\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        \n",
    "        @cache \n",
    "        def dfs(i: int) -> int:\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            if i == 1:\n",
    "                return 1\n",
    "            if i == 2:\n",
    "                return 1\n",
    "            return dfs(i - 1) + dfs(i - 2) + dfs(i - 3)\n",
    "        return dfs(n)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        dp = [0,1,1]\n",
    "        if 0 <= n <= 2:\n",
    "            return dp[n]\n",
    "        elif 3 <= n <= 37:\n",
    "            for i in range(3, n+1):\n",
    "                dp.append(dp[i-1] + dp[i-2] + dp[i-3])\n",
    "            return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        elif n == 1:\n",
    "            return 1\n",
    "        elif n == 2:\n",
    "            return 1\n",
    "        # return self.tribonacci(n-1) + self.tribonacci(n-2) + self.tribonacci(n-3)\n",
    "\n",
    "        a = 0\n",
    "        b = c = 1\n",
    "        for i in range(3, n + 1):\n",
    "            a,b,c = b,c,a+b+c \n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        a, b, c = 0, 1, 1\n",
    "        for _ in range(n):\n",
    "            a, b, c = b, c, a + b + c\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        elif n == 1 or n == 2:\n",
    "            return 1\n",
    "        t0 = 0\n",
    "        t1 = 1\n",
    "        t2 = 1\n",
    "        ti = t0 + t1 + t2\n",
    "        for i in range(3, n+1):\n",
    "            ti = t0 + t1 + t2\n",
    "            t0, t1 = t1, t2\n",
    "            t2 = ti\n",
    "        return ti"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        elif n == 1:\n",
    "            return 1\n",
    "        elif n == 2:\n",
    "            return 1\n",
    "        else:\n",
    "            res = [0, 1, 1]\n",
    "            for i in range(n-2):\n",
    "                res.append(res[-1]+res[-2]+res[-3])\n",
    "                # print(res)\n",
    "            return res[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        p = [0, 1, 1]\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        for i in range(3, n+1):\n",
    "            p.append(p[-1]+p[-2]+p[-3])\n",
    "        return p[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        t = [0, 1, 1]\n",
    "\n",
    "        for i in range(3, n+1):\n",
    "            t[i%3] = sum(t)\n",
    "        \n",
    "        return t[n%3]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        result_list = [0, 1, 1]\n",
    "        if n in [0, 1, 2]:\n",
    "            return result_list[n]\n",
    "        else:\n",
    "            for i in range(0, n+1, 1):\n",
    "                result_list.append(result_list[i+2] + result_list[i+1] + result_list[i])\n",
    "            return result_list[n]\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        '''\n",
    "        动态规划dp[i]=dp[i-1]+dp[i-2]+dp[i-3]\n",
    "        '''\n",
    "        a,b,c=0,1,1\n",
    "        if n==0:return 0\n",
    "        elif n==1 or n==2:return 1\n",
    "        else:\n",
    "            for _ in range(n-2):\n",
    "                a,b,c=b,c,a+b+c\n",
    "            return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        tri = [0,1,1]\n",
    "        if n<=2:\n",
    "            return tri[n]\n",
    "        for i in range(2,n):\n",
    "            tri.append(tri[i-2]+tri[i-1]+tri[i])\n",
    "        return tri[n]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        dp = [0, 1, 1]\n",
    "        if n <= 2:\n",
    "            return dp[n]\n",
    "        else:\n",
    "            for i in range(n-2):\n",
    "                T = dp[0]+dp[2]+dp[1]\n",
    "                dp[0], dp[1], dp[2] = dp[1], dp[2], T\n",
    "            return dp[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 0\n",
    "        if n==1 or n==2:\n",
    "            return 1\n",
    "        a=[0,1,1]\n",
    "        for i in range(n-2):\n",
    "            a.append(a[-1]+a[-2]+a[-3])\n",
    "        return a[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 0\n",
    "        if n <3:\n",
    "            return 1\n",
    "        dp = [0] *(n+1)#why +1 beacuse 第n个数 从0开始是n+1个\n",
    "        dp[0]=0\n",
    "        dp[1]=1\n",
    "        dp[2]=1\n",
    "        for i in range(3,n+1):\n",
    "            dp[i] = dp[i-1]+ dp[i-2]+ dp[i-3]\n",
    "        return dp[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        if n == 0 : return 0\n",
    "        if n == 1 or n == 2 : return 1\n",
    "\n",
    "        dp = [0 for k in range(n+1)]\n",
    "        dp[1] = dp[2] = 1\n",
    "        for k in range(3,n+1) :\n",
    "            dp[k] = dp[k-3] + dp[k-2] + dp[k-1]\n",
    "\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        dp = [0 for i in range(n+1)]\n",
    "        if n == 0:\n",
    "            dp[n] = 0\n",
    "        if n > 0 and n < 3:\n",
    "            dp[n] = 1\n",
    "        if n >=3 :\n",
    "            dp[0] = 0\n",
    "            dp[1] = 1\n",
    "            dp[2] = 1\n",
    "            j = 0\n",
    "            while j+3 <= n:\n",
    "                dp[j+3] = dp[j] + dp[j+1] + dp[j+2]\n",
    "                j += 1\n",
    "        return dp[n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1 or n == 2:\n",
    "            return 1\n",
    "        else:\n",
    "            p,q,r,s = 0,0,1,1\n",
    "            for i in range(n-2):\n",
    "                p,q,r = q,r,s\n",
    "                s = p+q+r\n",
    "            return s"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        a = {0: 0, 1: 1, 2: 1}\n",
    "        for i in range(3, n + 1):\n",
    "            a[i] = a[i - 1] + a[i - 2] + a[i - 3]\n",
    "        return a[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        a, b, c = 0, 1, 1\n",
    "        if n <= 1:\n",
    "            return n\n",
    "        for _ in range(n):\n",
    "            a, b ,c = b, c,a + b +c\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        f=[0,1,1]\n",
    "        i=3\n",
    "        while i<=n:\n",
    "            f.append(f[i-3]+f[i-2]+f[i-1])\n",
    "            i+=1\n",
    "        return f[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        if n < 2:\n",
    "            return n\n",
    "        if n == 2:\n",
    "            return 1 \n",
    "        dp = [0]*(n+1)\n",
    "        dp[1] = 1\n",
    "        dp[2] = 1\n",
    "        for i in range(3,n+1):\n",
    "            dp[i] = dp[i-1] + dp[i-2] + dp[i-3]\n",
    "        return dp[n]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        a, b, c = 0, 1, 1\n",
    "        if n <= 1:\n",
    "            return n\n",
    "        for _ in range(n):\n",
    "            a, b ,c = b, c,a + b +c\n",
    "        return a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        if n==1 or n==2:\n",
    "            return 1\n",
    "        elif n==0:\n",
    "            return 0\n",
    "        r = 2\n",
    "        a,b,c = 0,1,1\n",
    "        for i in range(3,n+1):\n",
    "            r = a+b+c\n",
    "            a,b,c = b,c,r\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        \n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1 or n == 2:\n",
    "            return 1\n",
    "        dp = [0] * (n+1)\n",
    "        dp[0] = 0\n",
    "        dp[1] = 1\n",
    "        dp[2] = 1\n",
    "        for i in range(n-2):\n",
    "            dp[i+3] = dp[i] + dp[i+1] + dp[i+2] \n",
    "        # print(dp)\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        if n == 1 or n == 2:\n",
    "            return 1\n",
    "        t0 = 0\n",
    "        t1 = t2 = 1\n",
    "        sum = 0\n",
    "        for i in range(2, n):\n",
    "            sum = t0 + t1 + t2\n",
    "            t0 = t1\n",
    "            t1 = t2\n",
    "            t2 = sum\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 0\n",
    "        if n<=2:\n",
    "            return  1\n",
    "        A=0\n",
    "        B,C=1,1\n",
    "        for i in range(3,n+1):\n",
    "            D=A+B+C\n",
    "            A,B,C=B,C,D\n",
    "        return D\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        elif n == 1:\n",
    "            return 1\n",
    "        elif n == 2:\n",
    "            return 1\n",
    "\n",
    "        x1, x2, x3 = 0, 1, 1\n",
    "        all_sum = 2\n",
    "        idx = 3\n",
    "        while idx < n:\n",
    "            tmp, x2, x3 = x2, x3, all_sum\n",
    "            all_sum += all_sum - x1\n",
    "            x1 = tmp\n",
    "            idx += 1\n",
    "        return all_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        dp = [0,1,1]\n",
    "        if n<3:\n",
    "            return dp[n]\n",
    "        for i in range(3,n):\n",
    "            num = dp[i-1]+dp[i-2]+dp[i-3]\n",
    "            dp.append(num)\n",
    "        \n",
    "        return dp[-1] + dp[-2] + dp[-3]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        a = [0,1,1]\n",
    "        for i in range(3,n+1):\n",
    "            a.append(a[i-1] + a[i-2]+a[i-3])\n",
    "        return a[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        dp = [0] * (n+1)\n",
    "        \n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1:\n",
    "            return 1\n",
    "        if n == 2:\n",
    "            return 1\n",
    "        dp[0], dp[1], dp[2] = 0, 1, 1\n",
    "        for i in range(3, n+1):\n",
    "            dp[i] = dp[i-3] + dp[i-1] + dp[i-2]\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        if n==0:\n",
    "            return 0\n",
    "        elif n==1 or n==2:\n",
    "            return 1\n",
    "        dp = [0 for _ in range(n+1)]\n",
    "        dp[0] = 0\n",
    "        dp[1] = dp[2] = 1\n",
    "        for i in range(3,n+1):\n",
    "            dp[i] = dp[i-1]+dp[i-2]+dp[i-3]\n",
    "        return dp[n]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        start_list = [0]*(n+3)\n",
    "        start_list[0] = 0\n",
    "        start_list[1] = 1\n",
    "        start_list[2] = 1\n",
    "        for x in range(3, n+1):\n",
    "            start_list[x] = (start_list[x-3]+start_list[x-2]+start_list[x-1]) \n",
    "        return start_list[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1 or n == 2:\n",
    "            return 1\n",
    "        if n > 2:\n",
    "            a, b, c = 0, 1, 1\n",
    "            for i in range(3,n+1):\n",
    "                temp = a + b + c\n",
    "                a, b, c = b, c, temp\n",
    "            return temp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n <= 2:\n",
    "            return 1\n",
    "        a, b, c = 0, 1, 1\n",
    "        for i in range(2, n):\n",
    "            tmp = a + b + c\n",
    "            a = b\n",
    "            b = c\n",
    "            c = tmp\n",
    "        return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        cache = {}\n",
    "\n",
    "        def tri(n):\n",
    "            if n in cache:\n",
    "                return cache[n]\n",
    "\n",
    "            if n == 0:\n",
    "                result = 0\n",
    "            elif n == 1 or n == 2:\n",
    "                result = 1\n",
    "            else:\n",
    "                result = tri(n-1) + tri(n-2) + tri(n-3)\n",
    "            cache[n] = result\n",
    "            \n",
    "            return result\n",
    "        \n",
    "        return tri(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        elif n == 1:\n",
    "            return 1\n",
    "        elif n == 2:\n",
    "            return 1\n",
    "\n",
    "        x1, x2, x3 = 0, 1, 1\n",
    "        all_sum = 2\n",
    "        for idx in range(3, n):\n",
    "            tmp, x2, x3 = x2, x3, all_sum\n",
    "            all_sum += all_sum - x1\n",
    "            x1 = tmp\n",
    "        return all_sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        dp = [0 for i in range(40)]\n",
    "        dp[0], dp[1], dp[2] = 0, 1, 1\n",
    "        for i in range (3, 38):\n",
    "            dp[i] = dp[i-1] + dp[i-2] + dp[i-3]\n",
    "        return dp[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        T = [0,1,1]\n",
    "        for i in range(3,n+1):\n",
    "            T.append(T[i-3] + T[i-2] + T[i-1])\n",
    "        return(T[n])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    arr={\n",
    "        0:0,\n",
    "        1:1,\n",
    "        2:1\n",
    "    }\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        for i in range(3,n+1):\n",
    "            self.arr[i]=self.arr[i-1]+self.arr[i-2]+self.arr[i-3]\n",
    "        return self.arr[n]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        if n == 0: return 0\n",
    "        if n == 1 or n == 2: return 1\n",
    "        f1 = 0\n",
    "        f2 = 1\n",
    "        f3 = 1\n",
    "        f4 = 0\n",
    "        for i in range(2, n):\n",
    "            f4 = f1 + f2 + f3\n",
    "            f1 = f2\n",
    "            f2 = f3\n",
    "            f3 = f4\n",
    "        return f4"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        if n == 0: return 0\n",
    "        elif n == 1 or n == 2: return 1\n",
    "        T0, T1, T2 = 0, 1, 1\n",
    "        for i in range(3, n + 1):\n",
    "            Tn = T0 + T1 + T2\n",
    "            T0, T1, T2 = T1, T2, Tn\n",
    "        return T2\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def tribonacci(self, n: int) -> int:\n",
    "        if n == 0:\n",
    "            return 0\n",
    "        if n == 1 or n == 2:\n",
    "            return 1\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[0] = 0\n",
    "        dp[1] = dp[2] = 1\n",
    "        for i in range(3, n + 1):\n",
    "            dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]\n",
    "        return dp[-1]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
